class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size() - 1;
        srand(time(nullptr));   // 种一颗随机种子
        // 快排
        return qsort(nums, 0, n, k);
    }

    // 快排选择
    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if(l == r)  return nums[l];

        // 1. 随机选择基准元素
        int key = getRandom(nums, l, r);
        // 2. 根据基准元素将数组分三块
        int cur = l, left = l - 1, right = r + 1;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[--right], nums[cur]);
        }

        // 3. 分情况讨论
        // 分为三块区间：[l, left] [left + 1, right] [right + 1, r]
        //              a 个元素    b 个元素         c 个元素
        int c = r - right + 1, b = right - 1 - (left + 1) + 1;
        if(c >= k) 
            return qsort(nums, right, r, k);
        else if(b + c >= k)
            return key;
        else
            return qsort(nums, l, left, k - b - c);
    }

    // 取基准值
    int getRandom(vector<int>& nums, int left, int right)
    {
        int key = rand();
        key = key % (right - left + 1) + left;
        return nums[key];
    }
};

//#################################################################################
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size() - 1;
        srand(time(nullptr));   // 种一颗随机种子
        qsort(nums, 0, n);      // 快排
        return nums[n - k + 1];
    }

    // 快排
    void qsort(vector<int>& nums, int l, int r)
    {
        if(l >= r)  return;

        // 数组分三块
        int key = getRandom(nums, l, r);
        int cur = l, left = l - 1, right = r + 1;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[--right], nums[cur]);
        }

        // 分为三块区间：[l, left] [left + 1, right] [right + 1, r]
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    // 取基准值
    int getRandom(vector<int>& nums, int left, int right)
    {
        int key = rand();
        key = key % (right - left + 1) + left;
        return nums[key];
    }
};